// 动态规划解题思路：
// 1)状态转移表：  画图表，for循环
// 2)状态转移方程：写递推公式，递归
// 贪心、回溯、动态规划类似，都可以抽象成多阶段决策最优解模型

#include <iostream>
#include <vector>
using std::cout;
using std::endl;

// 一、最短路径问题。有如下矩阵，每次只能向右或者向下移动一位，求左上角到右下角的最短路径和
/*
1 3 5 9
2 1 3 4
5 2 6 7
6 8 4 3
*/

typedef std::vector<std::vector<int>> Matrix;

// 1)状态转移表求解。「正着来」循环穷举
int MinDist1(const Matrix& matrix) {
  if (matrix.size() == 0) return -1;

  Matrix distNum(matrix.size());
  for (int i = 0; i < matrix.size(); i++) {
    distNum[i].resize(matrix[i].size());
  }

  distNum[0] = matrix[0];
  for (int i = 1; i < matrix.size(); i++) {
    for (int j = 0; j < matrix[i].size(); j++) {
      if (j == 0)
        distNum[i][j] = distNum[i - 1][j] + matrix[i][j];
      else
        distNum[i][j] =
            std::min(distNum[i - 1][j], distNum[i][j - 1]) + matrix[i][j];
    }
  }

  return distNum[distNum.size() - 1][distNum[0].size() - 1];
}

// 2)状态转移方程求解。「倒着来」递归/递推（假设上一步已知）
// RecurMinDist(i,j) = min(RecurMinDist(i-1,j), RecurMinDist(i,j-1)) + curDist
int RecurMinDist(const Matrix& matrix, int i, int j) {
  if (i == 0 && j == 0) {
    return matrix[i][j];  // 退出条件（真的已知）
  }
  int up = INT32_MAX;
  if (i - 1 >= 0) {
    up = RecurMinDist(matrix, i - 1, j);
  }
  int left = INT32_MAX;
  if (j - 1 >= 0) {
    left = RecurMinDist(matrix, i, j - 1);
  }
  return std::min(up, left) + matrix[i][j];
}

void TestMinDist() {
  Matrix matrix = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
  // print the matrix
  for (int i = 0; i < matrix.size(); i++) {
    for (int j = 0; j < matrix[i].size(); j++) {
      cout << matrix[i][j] << ' ';
    }
    cout << endl;
  }

  cout << "MinDist1: " << MinDist1(matrix) << endl;
  cout << "RecurMinDist: "
       << RecurMinDist(matrix, matrix.size() - 1, matrix[0].size() - 1) << endl;
}

// 二、硬币找零。比如有1,3,5三种面值硬币，求找9元给硬币数量最小的方案？

int main() { TestMinDist(); }